Introduction to Machine Learning

Chapter 07: Naive Bayes

1. Introduction

Naive Bayes is the simplest classifier in this course that is still genuinely competitive on real problems. It rests on Bayes' theorem plus one deliberately unrealistic assumption — that features are conditionally independent given the class — and that assumption is what makes it fast enough to train on a million documents.

We start from Bayes' theorem itself and the base-rate reasoning it enforces, derive the classification rule in log-space, then handle the practical problems: the zero-frequency trap and its Laplace smoothing fix, the three flavours of Naive Bayes (Gaussian, Multinomial, Bernoulli), and the vectorisation step — bag-of-words and TF–IDF — that turns raw text into something a classifier can consume. We close by benchmarking Naive Bayes against KNN and decision trees, and asking honestly where it fails.

Learning Objectives

2. Theory

2.1 Bayes' Theorem — Foundation of Naive Bayes

Reverend Thomas Bayes' 1763 theorem lets us update beliefs given evidence. For a class label \(y\) and feature vector \(x = (x_1, x_2, \dots, x_d)\):

\[ P(y \mid x) = \frac{P(x \mid y) \cdot P(y)}{P(x)} \]

2.2 The "Naive" Conditional Independence Assumption

The hard part is \(P(x \mid y) = P(x_1, x_2, \dots, x_d \mid y)\) — a full joint distribution over \(d\) features is exponentially hard. Naive Bayes makes a strong but computationally convenient assumption:

Naive Assumption: All features are conditionally independent given the class label.

\[ P(x \mid y) = \prod_{i=1}^{d} P(x_i \mid y) \]

This assumption is rarely true in a literal sense, since features are often correlated. Naive Bayes nevertheless works well in practice on tasks such as text classification, spam detection and sentiment analysis. The reason is that classification only depends on which class has the largest posterior, not on whether the posterior values themselves are accurate.

2.3 Naive Bayes Classification Rule

For a new sample \(x\), pick the class \(\hat{y}\) that maximizes the unnormalized log-posterior (log avoids numerical underflow and turns products into sums):

\[ \hat{y} = \arg\max_{y \in Y} \left[ \log P(y) + \sum_{i=1}^{d} \log P(x_i \mid y) \right] \]

2.4 In-Class Activity — Laplace-Smooth All Play-Golf Features

Recall the Play-Golf dataset with 5 "No" training rows. We already smoothed Outlook for "No" (|V|Outlook = 3). Complete the remaining three features for the "No" class with α = 1:

Temperature
Humidity
Windy
✅ Answers

Raw counts (Temp ∣ No): Hot=2, Mild=2, Cool=1. Total=5. |V|Temp = 3.

Compute smoothed P(Temp=Hot∣No), P(Mild∣No), P(Cool∣No).

Raw counts (Humidity ∣ No): High=4, Normal=1. Total=5. |V|Humidity = 2.

Compute smoothed P(High∣No), P(Normal∣No).

Raw counts (Windy ∣ No): False=2, True=3. Total=5. |V|Windy = 2.

Compute smoothed P(False∣No), P(True∣No).

  • Temp: (2+1)/(5+3)=3/8=0.375, (2+1)/8=0.375, (1+1)/8=2/8=0.25   (sum = 1 ✓)
  • Humidity: (4+1)/(5+2)=5/7≈0.714, (1+1)/7=2/7≈0.286
  • Windy: (2+1)/(5+2)=3/7≈0.429, (3+1)/7=4/7≈0.571

2.5 Three Flavors of Naive Bayes

The classification rule is the same in every case. What changes is how the likelihood \(P(x_i \mid y)\) is modelled, and that depends on the type of the features. This gives three standard variants:

VariantLikelihood ModelTypical FeaturesUse Case
GaussianNB \(P(x_i \mid y) = \mathcal N(\mu_{y,i}, \sigma^2_{y,i})\) Continuous numeric (cm, kg, °C) Iris / Wine / Breast-Wisconsin
MultinomialNB \(P(x_i \mid y)\) from normalized counts Word counts, integer frequencies Text (spam, sentiment, newsgroups)
BernoulliNB \(P(b_i \mid y) \in (0,1)\), binarized features Binary / presence-absence Short texts, binary user features

GaussianNB Numerics

GaussianNB fits a per-class per-feature normal distribution. For numerical stability, scikit-learn adds a tiny epsilon \(\epsilon=10^{-9}\) to every variance so no variance is ever exactly zero. Always scale/standardize numeric features if you want all features to contribute comparable Gaussian log-likelihood magnitudes.

2.6 From Raw Text to NB — Vectorization

Naive Bayes cannot operate on strings, so a document must first be converted into a fixed-length numeric vector. The two standard ways of doing this are counting words and weighting them by how informative they are.

E-mail text feature extraction pipeline An e-mail string is tokenized and then represented using Bag-of-Words, Binary Bernoulli, or TF-IDF features. Raw e-mail string Step A: TOKENIZE (lowercase, split) "WIN!! Free Money NOW" → "win free money now" 1 Bag-of-Words (CountVec) count(word) per doc d = |V| integer cols 2 Binary (Bernoulli) 1 (word present) per doc d = |V| binary cols 3 TF-IDF TF × IDF score per word reweights common words DOWN s*

2.7 TF-IDF Formalized

Term Frequency × Inverse Document Frequency weights down words that appear everywhere (the, a, of) and boosts words that are rare and hence discriminative.

\[ \text{tf-idf}(t, d, D) = \underbrace{f_{t,d}}_{\text{TF}} \;\times\; \underbrace{\log\frac{|D|}{|\{d' \in D \mid t \in d'\}|}}_{\text{IDF}} \]

2.8 Python scikit-learn Spam Pipeline (Conceptual)

Vectorization and classification are normally combined into a single pipeline, so that the vocabulary is learned from the training data only and the same transformation is applied at prediction time:

from sklearn.pipeline import Pipeline
from sklearn.feature_extraction.text import CountVectorizer, TfidfTransformer
from sklearn.naive_bayes import MultinomialNB
from sklearn.metrics import roc_auc_score
pipe = Pipeline([ ('vect', CountVectorizer(stop_words='english', min_df=5, ngram_range=(1,2))), ('tfidf', TfidfTransformer()), ('clf', MultinomialNB(alpha=0.5)) ])
pipe.fit(X_train, y_train)
y_proba = pipe.predict_proba(X_val)[:, 1]
print(f"Validation AUC: {roc_auc_score(y_val, y_proba):.4f}")

2.9 Benchmark — NB vs. kNN vs. Decision Trees

The following results compare Naive Bayes with the two classifiers studied earlier on three datasets of different character. They are indicative rather than definitive, but the pattern across dataset types is informative:

DatasetMetrickNN (k=5)NB (Gauss/Multi)Tree (depth 5)
Iris (num, 4f) Accuracy0.9670.960 (Gaussian)0.953
SMS Spam (text) AUC0.820.985 (MNB)0.90
Adult (mixed, 14f) AUC0.830.86 (MNB)0.88
Training time (relative)  10×1×3×
🔍 Benchmark Observations (click to expand)
  • NB wins big on text (SMS spam) — the conditional-independence assumption is surprisingly effective when features are words.
  • All three methods are competitive on clean, low-dimensional numeric data (Iris).
  • Decision Trees pull ahead on mixed tabular (Adult) because they model non-linear feature interactions and splits — something NB cannot do.
  • NB is consistently the fastest trainer by an order of magnitude — strong as a baseline first model.

2.10 When NB Works (and When It Fails)

The benchmark results follow directly from the independence assumption. It costs little when features carry largely separate information, and it costs a great deal when they do not:

👍 NB Shines When👎 NB Struggles When
Small training sets (low variance)Strongly correlated features exist
Text / high-dimensional sparse inputsYou need calibrated probabilities (use Platt scaling)
Streaming / incremental updates requiredFeature interactions drive the prediction
A low-compute baseline is neededNum features is tiny & signal is all-interaction

3. Interactive Examples

Example 1: GaussianNB on Iris

Two-class (Setosa vs. Virginica) slice of Iris. Fitted per-class Gaussian parameters (Petal-Length cm): Setosa: \(\mu=1.46,\; \sigma^2=0.03\); Virginica: \(\mu=5.55,\; \sigma^2=0.30\).

(a) A new flower has Petal-Length = 3.0 cm. Which class does GaussianNB favor?

Compute log-likelihood ratio using \(\log \mathcal{N} = -\frac{(x-\mu)^2}{2\sigma^2} - \log\sigma\). Ratio favors Setosa over Virginica by ~2.5 nats → predict Setosa. (3 cm is 5\(\sigma\) away from Virginica's mean, but only ~8\(\sigma\) from Setosa — Virginica's larger variance softens the blow but not enough!)

(b) Why is \(\sigma^2_{\text{Virginica}}=0.30\) so much larger than \(\sigma^2_{\text{Setosa}}=0.03\)?

Virginica petal lengths are genuinely more spread out in nature than Setosa's (which are tightly clustered). GaussianNB learns different per-class per-feature variances and uses them correctly.

Example 2: Benchmark Choice

A startup ships a spam filter on a Raspberry Pi (very low CPU) and must retrain daily on 100K new labeled emails. Accuracy is "good enough" at any score ≥ 0.95 AUC; training-time budget: 30 seconds.

Choose the best model from {kNN, GaussianNB, MultinomialNB, DecisionTree} and justify in 1 sentence.

MultinomialNB with TF-IDF: text input → multinomial is correct; MNB trains 10× faster than kNN and hits ≥ 0.98 AUC on SMS spam in the benchmark — comfortably above 0.95 within the time budget.

Example 3: Bayes' Theorem — Medical Diagnostic

A rare disease affects 1% of the population (\(P(D) = 0.01\)). A test is 99% sensitive (\(P(+ \mid D) = 0.99\)) and 95% specific (\(P(- \mid \neg D) = 0.95\)).

You test positive. What is \(P(D \mid +)\)?

Step 1: \(P(+ \mid \neg D) = 1 - 0.95 = 0.05\)

Step 2: Evidence = \(P(+) = P(+\mid D)\,P(D) + P(+\mid \neg D)\,P(\neg D) = 0.99 \cdot 0.01 + 0.05 \cdot 0.99 = 0.0594\)

Step 3: \(P(D \mid +) = \dfrac{0.99 \cdot 0.01}{0.0594} = \dfrac{0.0099}{0.0594} \approx \mathbf{16.7\%}\)

Even a 99%/95% accurate test has only ~17% PPV on a 1% prevalence disease (base-rate fallacy!) — always use Bayes.

Example 4: Spam Filter Prior Mismatch

Your spam classifier was trained on a public dataset where spam prevalence was 50%. You deploy it to a corporate inbox where only 2% of emails are spam.

Will the classifier over-predict or under-predict spam, and why?

Over-predict spam. The learned prior \(P(\text{spam}) = 0.50\) is 25× higher than the true prior \(P(\text{spam}) = 0.02\). Since the posterior is proportional to likelihood × prior, the inflated prior shifts predictions toward "spam" for borderline cases. Fix: re-estimate the prior from the deployment distribution (or use calibration).

4. Numerical Solutions

Problem 1: GaussianNB on 2-Class 2-Feature Toy Data

Class A (n=3): samples \((1,2), (2,3), (3,4)\) · Class B (n=3): \((6,7), (7,8), (8,9)\).

Classify the point \((4, 5)\) using GaussianNB.

Step 1: Class priors equal (3/6 each = 0.5).

Step 2: Fit Gaussians.

  • \(\mu_A = (2, 3),\; \sigma^2_A = (2/3, 2/3) \approx (0.667, 0.667)\)
  • \(\mu_B = (7, 8),\; \sigma^2_B = (2/3, 2/3) \approx (0.667, 0.667)\)

Step 3: Evaluate log-likelihood at \((4,5)\):

  • \(\log P(A)\) contrib \(= -\frac{(4-2)^2}{2 \cdot 0.667} - \frac{(5-3)^2}{2 \cdot 0.667} \approx -6.00\)
  • \(\log P(B)\) contrib \(= -\frac{(4-7)^2}{2 \cdot 0.667} - \frac{(5-8)^2}{2 \cdot 0.667} \approx -13.50\)

Step 4: argmax → Class A (by ~7.5 nats). Equal priors → pure likelihood fight, and \((4,5)\) is closer to A's center.

Problem 2: Naive Bayes — Spam vs. Ham

Training corpus: 40% spam (\(P(S)=0.4\)), 60% ham (\(P(H)=0.6\)). Word frequencies given the class:

Word\(P(\text{word} \mid S)\)\(P(\text{word} \mid H)\)
win0.600.05
free0.500.10
meeting0.050.50

A new email contains words: {win, free}. Classify it.

Step 1: Compute unnormalized log-posterior for SPAM:

\(\log 0.4 + \log 0.60 + \log 0.50 = -0.916 + (-0.511) + (-0.693) = \mathbf{-2.120}\)

Step 2: Compute unnormalized log-posterior for HAM:

\(\log 0.6 + \log 0.05 + \log 0.10 = -0.511 + (-2.996) + (-2.303) = \mathbf{-5.810}\)

Step 3: argmax → SPAM (\(-2.120 > -5.810\)).

Note: Normalization constant is same for both classes, so we skip it.

Problem 3: Prior × Likelihood Intuition

Now take the exact same vocabulary email {win, free}, but move to a company inbox where only 1% of mail is spam (\(P(S)=0.01,\; P(H)=0.99\)).

Does the classification change? Explain.

Step 1: log-posterior SPAM \(= \log 0.01 + \log 0.60 + \log 0.50 = -4.605 - 0.511 - 0.693 = \mathbf{-5.809}\)

Step 2: log-posterior HAM \(= \log 0.99 + \log 0.05 + \log 0.10 = -0.010 - 2.996 - 2.303 = \mathbf{-5.309}\)

Step 3: argmax → HAM (\(-5.309 > -5.809\)).

Moral: The same email flips classification because the prior changed. When spam is rare (1%), the evidence of two spammy words isn't strong enough to overcome the low base rate. This is why priors matter!

Problem 4: Laplace-Smoothing Parameter Sweep

Rare-word case: vocabulary size \(|V| = 10{,}000\). In Class \(Y=+\), a rare word "antidisestablishmentarianism" has \(\text{count}(w, +) = 0\) and \(\text{count}(+) = 1000\).

Evaluate the smoothed probability \(P_s(w \mid +, \alpha)\) at different values of \(\alpha\).

\(P_s(w\mid +,\alpha) = \frac{0+\alpha}{1000 + 10000\alpha}\). Evaluated at different \(\alpha\):

  • \(\alpha = 0 \rightarrow 0\) (broken — zero frequency problem)
  • \(\alpha = 1 \rightarrow 1/11000 \approx 9.1 \times 10^{-5}\)
  • \(\alpha = 0.1 \rightarrow 0.1/(1000+1000) = 5 \times 10^{-5}\)
  • \(\alpha = 10 \rightarrow 10/(1000+100000) \approx 9.9 \times 10^{-5}\)

Small \(\alpha\) = trusts the data more (closer to MLE); large \(\alpha\) = smooths toward uniform \(1/|V|\). Best \(\alpha\) is tuned on a validation set!

5. Try It Yourself

Problem 1: GaussianNB Classification

Classes: A (\(\mu=0, \sigma^2=1\)), B (\(\mu=4, \sigma^2=4\)), equal priors. Classify \(x = 1.5\).

  1. Compute log-likelihood for A and for B.
  2. Which class wins? By how many nats?
  1. \(\log \mathcal{L}(A) = -\frac{(1.5)^2}{2} - \log(1) \approx -1.125\)
    \(\log \mathcal{L}(B) = -\frac{(1.5-4)^2}{2 \cdot 4} - \frac{1}{2}\log(4) \approx -0.781 - 0.693 \approx -1.474\)
  2. Class A wins by about 0.35 nats (despite B having a flatter, wider Gaussian, \(x=1.5\) is much closer to 0 than to 4).

Problem 2: Bayes' Theorem in a Factory

Factory machines M1, M2, M3 produce 20%, 30%, 50% of total output respectively. Their defect rates are 5%, 3%, 1%. An item is randomly sampled and found defective.

Which machine is it most likely to have come from? Compute all 3 posteriors.

\(P(\text{def}) = 0.2 \cdot 0.05 + 0.3 \cdot 0.03 + 0.5 \cdot 0.01 = 0.01 + 0.009 + 0.005 = 0.024\)

  • \(P(M_1 \mid \text{def}) = \frac{0.010}{0.024} \approx 41.7\%\)
  • \(P(M_2 \mid \text{def}) = \frac{0.009}{0.024} = 37.5\%\)
  • \(P(M_3 \mid \text{def}) = \frac{0.005}{0.024} \approx 20.8\%\)

Most likely: Machine M1 (despite producing only 20% of items, its 5% defect rate dominates the posterior).

Problem 3: Naive Bayes Play-or-Not

Sports dataset: 9 play days, 5 no-play days. Weather frequencies given class:

Outlook\(P(\cdot \mid \text{Play})\)\(P(\cdot \mid \text{No})\)
Sunny2/93/5
Overcast4/90/5
Rain3/92/5

Classify Outlook = Overcast (apply Naive Bayes; use 1-sample Laplace smoothing where necessary).

Unnormalized posterior (Play) \(= (9/14) \times (4/9) = 36/126 \approx 0.286\)

Unnormalized posterior (No) \(= (5/14) \times (0/5) = 0 \leftarrow \text{zero!}\)

With Laplace smoothing (\(\alpha=1\)) on likelihood:

\(P(\text{Overcast} \mid \text{No}) = \frac{0 + 1}{5 + 3} = 1/8\)

Smoothed posterior (No) \(= (5/14) \times (1/8) \approx 0.045\)

argmax → Play (\(0.286 > 0.045\)).

Problem 4: BernoulliNB Play Golf

We convert the 4-category Outlook feature into 3 Bernoulli dummy features (IsSunny, IsOvercast, IsRain). What is \(P(\text{IsOvercast} \mid \text{No}, \alpha=1, |V|=2)\)?

Hint: We're now working per dummy, so vocabulary size is 2 (true/false). The No class has 5 training rows.

\(\text{count}(\text{IsOvercast}=T, \text{No}) = 0\), \(\text{count}(\text{No})=5\).
\(P_s = \frac{0 + 1}{5 + 2} = \mathbf{1/7 \approx 0.143}\).
(This is the same "rare event with smoothing" situation — BernoulliNB dummies just make each binary feature explicit.)

Problem 5: NB Incremental Throughput

Batch 1: 1,000,000 docs (700K spam, 300K ham). Count("sale" | spam) = 200K; Count("sale" | ham) = 6K.
Batch 2: 100,000 new docs arrive. Count("sale" | spam) = 18K; Count("sale" | ham) = 500.

(i) What are the merged counts? (ii) What are the merged \(P(\text{"sale"} \mid \text{spam})\) and \(P(\text{"sale"} \mid \text{ham})\) without smoothing?

Merged spam docs: 700K + ? — need to solve Batch 2 spam/ham split!

Assume Batch 2 class distribution is 50K spam / 50K ham for the problem:

  • Merged spam = 700K + 50K = 750K. Merged ("sale" | spam) = 200K + 18K = 218K \(\rightarrow P = 218\text{K}/750\text{K} \approx \mathbf{0.291}\).
  • Merged ham = 300K + 50K = 350K. Merged ("sale" | ham) = 6K + 500 = 6,500 \(\rightarrow P = 6.5\text{K}/350\text{K} \approx \mathbf{0.0186}\).

LR("sale") \(\approx 0.291 / 0.0186 \approx 15.6\times\) strong spam signal.

6. Interactive Quiz

Answer all 7 questions. Click an option for instant feedback.

Your score: 0 / 7

7. Key Takeaways

  1. Explained Variance Ratio: \(\text{EVR}_j = \lambda_j / \sum_i \lambda_i\). The scree plot visualizes EVR and the elbow guides \(k\)-selection (common thresholds: 90%, 95%, or the "elbow").
  2. Variance is conserved under PCA rotation: Sum of eigenvalues = Sum of original feature variances. PCA doesn't "lose" information globally — it reorganizes variance into orthogonal axes.
  3. Standardize before PCA whenever feature scales differ. Without standardization, income (in dollars) will dominate PCA over temperature (in °C).
  4. In the case study, PCA generalized best (highest test AUC), Wrapper overfit (highest train AUC, slowest), Filter was fastest with near-baseline quality. No single method is always best — run the experiment.
  5. Bayes' Theorem: \(P(y \mid x) = P(x \mid y)P(y)/P(x)\). The prior \(P(y)\) is critical. A "99 % accurate" test on a rare disease still gives a low posterior.
  6. Naive Bayes assumes conditional feature independence: \(P(x \mid y) = \prod P(x_i \mid y)\). Take logs to turn products into sums and avoid underflow. Works extremely well on text despite the "naive" assumption.
  1. Laplace smoothing applies to every feature. Use the vocabulary size \(|V_i|\) of that specific feature in the denominator. Don't reuse one feature's |V| for another.
  2. 3 NB variants for 3 data types: GaussianNB = continuous features; MultinomialNB = integer/count (bag-of-words text); BernoulliNB = binary presence/absence.
  3. Text → fixed vectors via CountVectorizer or TF-IDF. IDF crushes near-universal words (the, of, and) automatically, letting rare discriminative words dominate.
  4. NB is speed king for text — 10× faster than kNN, 3× faster than shallow trees, with best-in-class AUC on text. Use NB as your first baseline before trying expensive models.
  5. Incremental merging is exact. Add frequency tables element-by-element for every mini-batch. Recomputing from scratch is wasteful and unnecessary!
  6. Bias-variance intuition: NB has high bias (strong independence assumptions) but extremely low variance — it wins in small-data / high-d regimes where low-variance methods dominate.

8. Common Pitfalls

  1. Forgetting to standardize before PCA. The resulting PCs will be meaningless if features are on incomparable scales. Always use StandardScaler for heterogeneous data.
  2. Fitting PCA on the full dataset before train/test splitting. This leaks test-set distribution information. Fit on train only, then apply the learned \(W\) to both train and test.
  3. Interpreting individual PCA components as meaningful "features." PCs are linear combinations of all original features and are often not human-interpretable. Use factor analysis if interpretability is critical.
  4. Multiplying probabilities directly in Naive Bayes (not log space). For even moderate \(d\), \(\prod P(x_i \mid y)\) underflows to zero on floating-point hardware. Always use log-space arithmetic.
  5. Zero-frequency problem (P(word∣class)=0). A single unseen feature zeros the entire posterior. Always use Laplace (add-α) smoothing on categorical Naive Bayes likelihoods.
  6. Confusing "Wrapper overfits on training" with "Wrapper is useless." Wrappers are valid — you just need to couple them with strong regularization, a holdout validation set, and/or use them only on small feature subsets.
  1. Using GaussianNB on bag-of-words counts. BOW integers are not normally-distributed — use MultinomialNB instead. The mismatch usually costs 5–10 % AUC.
  2. Applying raw CountVectorizer without min_df / stop-words / pruning. 10⁵+ vocabulary blows up memory; hapax legomena (words seen once) hurt generalization.
  3. Sharing the same α across all NB variants blindly. α=1 (Laplace) is a default; for MultinomialNB on text, tune α ∈ {0.1, 0.5, 1, 2} on a validation set to squeeze out 1–2 % AUC.
  4. Interpreting NB's predicted probabilities as well-calibrated. The independence assumption distorts magnitudes. Use Platt scaling / isotonic regression via CalibratedClassifierCV if calibrated probabilities matter.
  5. TF-IDF on already-normalized likelihoods. Apply TF-IDF to the raw count matrix, then feed the reweighted matrix to MultinomialNB — don't try to apply it after NB training (too late).
  6. Benchmarking a single train-test split only. NB is stable but always use 5-fold CV with fixed random seed when comparing models — a lucky split can easily lie by 3 %.